package primary.primary0;

/**
 *
 * 总之就是不能重复计算。
 * 因为是对数次的计算，所以创建个数组保存中间计算结果也不靠谱
 */
public class S0050Pow {

    /**
     * 注意n的范围极大，但是x^n的数据范围很有限
     * 精度是怎么玩的?
     */
    public static void main(String[] args) {
        System.out.println(3 - (3/ 2) * 2);
        System.out.println(new Solution3().myPow(1, -2147483648));
    }

    /**
     * 答案之一，迭代，也是个办法
     *
     *
     */
    class Solution5 {
        public double myPow(double x, int n) {
            long N = n;
            return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
        }

        public double quickMul(double x, long N) {
            double ans = 1.0;
            // 贡献的初始值为 x
            double x_contribute = x;
            // 在对 N 进行二进制拆分的同时计算答案
            while (N > 0) {
                if (N % 2 == 1) {
                    // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
                    ans *= x_contribute;
                }
                // 将贡献不断地平方
                x_contribute *= x_contribute;
                // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
                N /= 2;
            }
            return ans;
        }
    }

    /**
     * 答案之一，int转long避免 -N在n = Integer.MIN_VALUE出现的问题。
     */
    class Solution4 {
        public double myPow(double x, int n) {
            long N = n;
            return N >= 0 ? quickMul(x, N) : 1.0 / quickMul(x, -N);
        }

        public double quickMul(double x, long N) {
            if (N == 0) {
                return 1.0;
            }
            double y = quickMul(x, N / 2);
            return N % 2 == 0 ? y * y : y * y * x;
        }
    }


    /**
     * 100, 感觉做过这题。
     */
    public static class Solution3{

        public double myPow(double x, int n) {
            // 当 n = -2147483648的时候，-n是-2147483648，这个正负号要注意
//            return n >= 0? doMyPow(x, n): 1 / doMyPow(x, -n);
            return doMyPow(x, n);
        }

        public double doMyPow(double x, int n){
            if(n == 0){
                return 1;
            }
            if(n == 1){
                return x;
            }
            if(n == -1){
                return 1/x;
            }
            return powSeco(doMyPow(x, n / 2)) * doMyPow(x, n - (n/2) * 2);
        }
        public double powSeco(double x){
            return x * x;
        }
    }
    public static class Solution2{

        private static double[] record;
        public double myPow(double x, int n) {
            // 这里n = 2^31 的时候，变成负数了
            record = new double[Math.abs(n)];
            return n >= 0? doMyPow(x, n): 1 / doMyPow(x, -n);
        }

        public double doMyPow(double x, int n){
            if(n == 0){
                return 1;
            }
            if(n == 1){
                return x;
            }
            if(record[n - 1] != 0){
                return record[n - 1];
            }
            double res = doMyPow(x, n / 2) * doMyPow(x, n - n / 2);
            record[n - 1] = res;
            return res;
        }
    }
    public static class Solution1{

        private static double[] record;
        public double myPow(double x, int n) {
            // 这里n = 2^31 的时候，加一变成负数了
            record = new double[Math.abs(n) + 1];
            return n >= 0? doMyPow(x, n): 1 / doMyPow(x, -n);
        }

        public double doMyPow(double x, int n){
            if(n == 0){
                return 1;
            }
            if(n == 1){
                return x;
            }
            if(record[n] != 0){
                return record[n];
            }
            double res = doMyPow(x, n / 2) * doMyPow(x, n - n / 2);
            record[n] = res;
            return res;
        }
    }


    /**
     * 这种拙劣的二分，和逐个计算一点区别没有。中间结果仍然被计算了很多次。
     */
    public double myPow4(double x, int n) {
        if(n == 1){
            return x;
        }
        if(n == 0){
            return 1;
        }
        if(n == -1){
            return 1/x;
        }
        return myPow4(x, n / 2) * myPow4(x, n - (n / 2));
    }

    /**
     * 会超时，所以目测是想让人用二分法
     */
    public double myPow3(double x, int n) {
        double res = 1;
        for(int i = 0; i < Math.abs(n); i++){
            res *= (n > 0? x: 1/x);
        }
        return res;
    }


    /**
     * 100, 。。源码很复杂。
     */
    public double myPow2(double x, int n) {
        return Math.pow(x, n);
    }
}
